package LearnDataStructure.c_树结构.例题;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;
/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-12 19:29
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */
/*
 * 给定排序（递增顺序）的阵列，
 * 编写一个算法来创建一个高度最小的二进制搜索树。
 */
public class d_创建高度最小二叉树根据递增数组 {

    public static void main(String[] args) {
        d_创建高度最小二叉树根据递增数组 test = new d_创建高度最小二叉树根据递增数组();
        b_MyBinaryTreebyLinked<Integer, Integer> Btree = new b_MyBinaryTreebyLinked<>();
        int[] arr = new int[] {2,4,6,7,8,9,10};
        Btree.setRoot(test.useCreateMinHeightTree(arr));
        System.out.println(Btree);
    }

    public BSTNode<Integer,Integer> useCreateMinHeightTree(int[] arr) {
        BSTNode<Integer, Integer> root = createMinHeightTree(arr, 0, arr.length - 1);
        return root;
    }

    private BSTNode<Integer, Integer> createMinHeightTree(int[] arr, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = start + ((end - start) >> 1);
        BSTNode<Integer, Integer> left = createMinHeightTree(arr, start, mid - 1);
        BSTNode<Integer, Integer> right = createMinHeightTree(arr, mid + 1, end);
        BSTNode<Integer, Integer> result = new BSTNode<>(arr[mid], null, left, right, null);
        if (left != null) {
            left.parent = result;
        }
        if (right != null) {
            right.parent = result;
        }
        return result;
    }
}
